1. Field of the Invention:
The present invention relates to the computer-aided design of integrated circuits, and more particularly to the automated optimization of component placement to ensure that timing constraints on all paths in such circuits can be met upon routing of the interconnections between the placed components.
2. Background of the Related Art:
Integrated circuit processing technology presently permits the creation of monolithic integrated circuits that involve millions of transistors. Due to the sheer number of devices on a single chip, an entire industry has evolved specifically to supply the semiconductor industry with software and hardware tools with which to automate much of the integrated circuit design process. In particular, significant research and development effort has been directed to effecting optimal placement of each component on the chip not only to minimize die area, but also to meet critical timing requirements of the various signal paths established through routing of the interconnect between the various components of the circuit.
A signal path of a circuit typically comprises a series of components as well as the segments of interconnect by which a signal travels from the output drivers of one of the series of components to the input of another. Critical paths are typically those which present relatively little headroom (also known as slack) for increases in path delay due to parasitics introduced by the segments of interconnect. As the feature sizes of components have continued to shrink over the past decade, the intrinsic delay through these devices has decreased commensurately. As a result, delays resulting from the parasitic loads presented to these components have become the predominate constituent of signal propagation delay through the paths of such circuits.
Thus, whether a critical path meets its timing constraint can be greatly affected by the length of interconnect segments that directly couple the components comprising the critical path, as well as the total length of the interconnect that couples each of the path segments to the inputs of other components of the circuit. The relative placement of the components of the circuit prior to interconnect routing therefore directly impacts the contribution of interconnect parasitics to the total delay experienced by a signal as it propagates through a path.
The process of automated chip design generally begins with a description of the desired chip function in VHDL (Verilog Hardware Description language) or a similar language. This functional description of the circuit is used to simulate the desired operation. Once verified, the functional description is input into a synthesis tool which extracts, from the description, hardware components and the interconnections requisite to implement the described functionality. The synthesis tool outputs the extracted physical representation of the circuit in the form of a netlist, which lists the components and their respective interconnections. The components can be individual circuit elements such as transistors, or they can be more complex cells or modules which comprise a number of circuit elements which are already themselves optimally placed and connected to perform standard functions. A "place-and-route" tool is then typically used to physically place the components defined by the netlist in two-dimensional space and then routes the conductive interconnections (i.e. nets) between each component's output and the input pins of other components as defined by the netlist. A net comprises one or more branches of interconnect, each branch connecting the output pin of one component to an input pin of another component. A circuit path is comprised of a series of segments, each segment encompassing a component and the interconnect branch which couples it to the input of the next component in the path.
During functional simulation of the integrated circuit design, a number of paths can be first identified as time critical. For example, an output signal of a first component might be required to propagate through a particular path of components and be available at the input of another component prior to arrival of, for example, a clock signal. In addition, synchronous clock signals that are supposed to arrive at inputs of numerous components throughout a circuit simultaneously may become skewed in time based on unequal propagation delays caused by varying interconnect lengths. Thus, in either case there is a maximum amount of time by which these signals can be delayed through a path such that the circuit will still operate properly. A critical path is typically one which has a relatively small margin for additional delay introduced by the parasitics of its interconnect. Of course, paths which are not be considered critical prior to component placement might become so if too much attention is paid to optimizing the most critical paths. A method for identifying critical paths is disclosed in "Critical Path Issues in VLSI Designs," H. Youssef et. al., IEEE International Conference on Computer-Aided Design, 1989, P. 520, which is incorporated herein by this reference.
There are a number of constituents which add up to the delay D.sub.P experienced by a signal propagating through a path. First, there is the intrinsic delay D.sub.i presented by each circuit component in the path through which a signal is transmitted. D.sub.i is the time necessary for the signal to propagate through the component (i.e. input to output) with no load.
A second constituent of D.sub.P is the delay experienced by the output driver of each component in the path in driving the capacitive load presented to it. The load presented to each driver of a path includes the total input capacitance C.sub.in, which is the sum of the input capacitances of all of the components to which it is coupled through its net, and the capacitance C.sub.W of the physical interconnect comprising its net. The ability of the driver of each component to drive its load, C.sub.in +C.sub.W, is called its effective resistance S, which when multiplied by the sum of C.sub.in and C.sub.W equals the delay incurred in driving those capacitances.
A third constituent of D.sub.P is the delay D.sub.RC experienced by the signal in propagating along the branch of interconnect between the output pin of the component of each segment of the path and the input pin of the component of the next segment. Thus, the equation defining the total delay D.sub.S experienced by a signal through each segment of a path in a circuit is D.sub.S =D.sub.i +S.multidot.(C.sub.in +C.sub.W)+D.sub.RC. The total delay through the path D.sub.P is then simply the sum of the segment delays for the path.
The intrinsic delay of the component D.sub.i, the total input capacitance of the inputs of the components driven by the output of the component C.sub.in, and the effective resistance of the component's driver S are constituents governed by circuit design considerations which are considered during the synthesis or generation of the netlist and do not vary as a function of interconnect length. The components identified in the netlist are selected from cell libraries or designed in contemplation of such characteristics. Because die area minimization is always a consideration, and given that a driver's effective output resistance S is inversely proportional to its size, it will not usually be desirable to select components which have substantially less effective resistance S than is necessary to meet the timing constraints. Thus, it is important to minimize the amount of interconnect length, particularly the length of the interconnect coupled into critical paths, to minimize those increasingly more dominant components of the path delay D.sub.P which are affected by wire length, namely S.multidot.C.sub.W and D.sub.RC.
The first placement techniques were net-based in character. Net-based techniques do not deal directly with the paths of a circuit, but rather act on the circuit nets each of which are typically coupled into multiple paths. The first net-based placement techniques simply attempted to minimize the total wire length of all of the nets in the circuit. A number of these techniques are based on a minimization algorithm known as the "mincut method." The mincut method iteratively cuts the chip into smaller and smaller equal sections using a cut-line. The method attempts to place the components on either side of the cut-line to minimize the number of nets or net segments which cross the cut-line. An area constraint is placed on the algorithm so that it splits the total area divided by the cut-line roughly in half and this proportion is maintained between the two sections during minimization. An example of a mincut method is disclosed in "A Linear-Time Heuristic for Improving Network Partitions," C. M. Fiducccia and R. M. Mattheyses, Paper 13.1, 19th Design Automation Conference, IEEE, 1982, and which is incorporated herein by this reference.
While an approach that simply reduces overall net length may reach a placement solution which minimizes die area and reduces overall parasitic capacitance due to interconnect, it cannot by itself ensure that timing constraints on specific paths will be properly met. Thus, attempts have been made to adapt net-based techniques to take account of critical paths in the circuit; put another way, to make them timing-driven. One simple technique places a maximum permissible capacitance on nets which are coupled to critical paths to prevent them from exceeding their timing constraints. A more sophisticated technique imposes a cost-weighting function to the nets coupled to identified critical paths, the weights being used to bias place and route tools into minimizing those nets at the expense of nets not coupled into critical paths. Typically, the critical paths are identified prior to layout and weights are assigned to the nets coupled to those nets based on an assessment of how much headroom (e.g. slack) is present for each critical path (i.e. the difference between the maximum permissible path delay and an initial estimate of the path delay taking interconnect into account).
The above-described weighting technique permits the initial path delay to be based on some arbitrary estimate of the interconnect for the nets coupled to the path, or on path delays calculated for each critical path based on an actual initial placement. The weights are used to bias priorities associated with placement and routing tools. The circuit is then simulated based on the resulting layout and if critical timing requirements have not been met, the layout is adjusted and resimulated until the constraints are met. An example of this technique is disclosed in "Chip Layout Optimization Using Critical Path Weighting," A. E. Dunlop, et al., Paper 9-2, ACM/IEEE 21st Design Automation Conference, 1984, the text of which is incorporated herein by this reference.
While the foregoing timing-driven weighting techniques skew the minimization of net lengths (and thus net capacitance) in favor of those nets coupled into critical paths, they neither check placement during the layout process to determine whether critical path timing constraints are being met, nor do they update the weighting in accordance with the changing layout producing varying interconnect lengths defined by each placement iteration. As iterations of placement occur, the actual length of any given net can vary such that paths that were considered critical at the start of the placement process may have become less so, whereas other paths originally thought non-critical may have become critical.
A further refinement of this net-weighting technique calculates path delays after each placement iteration for those paths having been initially identified as critical. This technique employs a constraint engine by which the timing constraint of each critical path is converted to a net weight that is assigned to each of the nets coupled into that path, the magnitude of the weight being commensurate with how critical the path is (i.e. how little slack the path has). Iterative net-weighting techniques typically employ a variation of the mincut algorithm such that the total weight of all nets or segments of nets crossing the cut-line is minimized by moving the components from one side of the cut-line to the other. After each iteration of the mincut algorithm, the constraint engine recalculates the path delays and the slack for the critical paths based on the new placement resulting from the previous iteration and reassigns new net weights based on the current slack value for each critical path.
Because of the time-consuming calculations which must be made by the constraint engine and the mincut algorithm, it is not practicable to constrain and update all nets in a circuit in the above-described manner. Thus, some paths which are deemed not critical initially may become critical once nets coupled to them are sacrificed in length for others deemed more critical. Further, because the nets coupled to a critical path are assigned the same weight, components in a path which is bisected by the cut-line will not necessarily be moved to the same side of the cut-line because such moves will not provide a gain to the minimization algorithm. Thus, the algorithm must rely on hill-climbing techniques to avoid local minima which are encountered along paths. It is well-known that hill-climbing techniques, which make a series of moves that either provide zero or even negative gain to discover larger gains, are not guaranteed to discover the benefits of shortening the paths themselves. Thus, D.sub.RC and S.multidot.C.sub.W are not guaranteed to be minimized.
The shortcoming of all of the foregoing net-based techniques is that they place constraints on nets even though it is the paths of the circuit that have critical timing requirements. Thus, the path delays are only indirectly affected by the minimization of the nets which are coupled to the paths. The minimization of net capacitance driven by elements in a critical path is only one of the constituents of the load which is driven by the element; the other constituent is the delay experienced by the signal as it travels the path segment between the ouput of one element in the path and the input of the next element in the path. These techniques therefore do not minimize the D.sub.RC component of each segment D.sub.S.
A second class of timing-driven placement methods has evolved that determine component placement based directly on calculations of path delay for each of the critical paths. Thus, the interconnect coupled into a critical path, including the segments of nets coupling the components of the path, is directly constrained based on delay calculations for the path rather than indirectly through weighted minimization of nets coupled into the path. The critical paths are guaranteed to meet their timing constraints if at all possible. Those critical paths which are currently meeting their timing constraints are optimized for wire length and area, while those paths which are not meeting their constraints are optimized for delay at the expense of other areas of the circuit if necessary. These path-based techniques, like mincut minimizations, often break the circuit into sub-areas. They then analyze the delay through individual path segments, making the coordinate location of the various components a complex mathematical function of the parameters defining path delay. These path-based techniques, while able to constrain paths directly rather than indirectly by constraining the nets coupled into the path, are extremely computation intensive and thus time consuming. As a result they are typically restricted to a relatively small number of critical paths. Otherwise, they would risk not reaching a solution within a reasonable period of time. As with net-based techniques, some paths may become critical which were not originally deemed critical because they are not being constrained. Examples of timing-driven path-based placement techniques are disclosed in Ritual: A Performance Driven Placement Algorithm, by Arvind Srinivasan, Kamal Chaudhary, and E. S. Kurth, Memorandum No. UCB/ERL M91/103, Nov. 19, 1991; and W. E. Donath, et at., "Timing Driven Placement Using Complete Path Delays," 27th ACM/IEEE Design Automation Conference, 1990, pp. 84-89.
Because layout is primarily concerned with routing nets rather than paths, it is it is more efficacious to use net-based constraints on placement. Because critical timing problems are path-based, however, direct constraints on placement must somehow be imposed based on path delay. Therefore, there is room in the art for a placement methodology that imposes a direct influence on path delays during placement using net-based constraints, which does not permit paths which are not critical to become critical at the expense of those paths initially identified as critical, and is capable of reaching a solution within a reasonable period of time.